// run: $exec < input
#include <iostream>
#include <algorithm>
#include <vector>

int const maxn = 110000;
long long a[maxn], sum[maxn];
int n, m;

struct line { int k, b; };

bool operator<(line const & a, line const & b)
{
	return a.k > b.k || (a.k == b.k && a.b < b.b);
}

double intersect(line const & a, line const & b)
{
	return (b.b - a.b) / double(a.k - b.k);
}

line lines[maxn], tmp[maxn];

struct node
{
	std::vector<line> convex;
	std::vector<double> poi; // point of intersection
	void build(int l, int r);
	int query(int x);
};

void node::build(int l, int r)
{
	for (int i = l; i <= r; i++) tmp[i - l] = lines[i];
	int len = r - l + 1;
	std::sort(tmp, tmp + len);
	for (int i = 0; i < len; i++) {
		if (!convex.empty() && convex.back().k == tmp[i].k) continue;
		while (convex.size() >= 2) {
			int s = convex.size();
			if (intersect(convex[s - 2], convex[s - 1]) < intersect(convex[s - 1], tmp[i]))
				break;
			convex.pop_back(); poi.pop_back();
		}
		if (!convex.empty()) poi.push_back(intersect(convex.back(), tmp[i]));
		convex.push_back(tmp[i]);
	}
}

int node::query(int x)
{
	int id = std::lower_bound(poi.begin(), poi.end(), x) - poi.begin();
	int ret = convex[id].k * x + convex[id].b;
	if (id + 1 < (int)convex.size())
		ret = std::min(ret, convex[id + 1].k * x + convex[id + 1].b);
	if (id - 1 >= 0)
		ret = std::min(ret, convex[id - 1].k * x + convex[id - 1].b);
	return ret;
}

node tree[4 * maxn];

int segment_tree_query(int id, int l, int r, int tl, int tr, int x)
{
	if (l == tl && r == tr) return tree[id].query(x);
	int mid = (l + r) / 2;
	if (tr <= mid) return segment_tree_query(id * 2, l, mid, tl, tr, x);
	else if (tl > mid) return segment_tree_query(id * 2 + 1, mid + 1, r, tl, tr, x);
	else return std::min(segment_tree_query(id * 2, l, mid, tl, mid, x),
							segment_tree_query(id * 2 + 1, mid + 1, r, mid + 1, tr, x));
}

void segment_tree_build(int id, int l, int r)
{
	tree[id].build(l, r);
	if (l == r) return;
	int mid = (l + r) / 2;
	segment_tree_build(id * 2, l, mid);
	segment_tree_build(id * 2 + 1, mid + 1, r);
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	// K*X + B, K = a[l],  B = a[l] * l - sum[l]
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
		lines[i].k = -a[i];
		lines[i].b = a[i] * i - sum[i];
	}
	segment_tree_build(1, 1, n);
	std::cin >> m;
	for (int i = 0, x, y; i < m; i++) {
		std::cin >> x >> y;
		std::cout << segment_tree_query(1, 1, n, y - x + 1, y, y - x) + sum[y] << '\n';
	}
}

